// https://www.lintcode.com/problem/rotate-string-ii/

public class Solution {
    /**
     * @param str: A String
     * @param left: a left offset
     * @param right: a right offset
     * @return: return a rotate string
     */
    public String RotateString2(String str, int left, int right) {
        // write your code here
        StringBuilder sb = new StringBuilder(str);
        int ls = -1, rs = -1, shift = -1;
        int slen = str.length();
        left %= slen;
        right %= slen;
        if (right > left) {
            rs = right - left;
            shift = slen - rs;
        } else if (left > right) {
            ls = left - right;
            shift = ls;
        }
        if (shift > 0) {
            reverse(sb, 0, shift);
            reverse(sb, shift, slen);
            reverse(sb, 0, slen);
        }
        return sb.toString();
    }
    
    protected void reverse(StringBuilder sb, int start, int end) {
        --end;
        while (start < end) {
            Character c = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, c);
            ++start;
            --end;
        }
    }
}